﻿#pragma once
#include "Index.h"

class IFindAllAnagramsInAString
{
public:
	/**
	 * 找到字符串中所有字母异位词.
	 * https://leetcode.cn/problems/find-all-anagrams-in-a-string/
	 *
	 * 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
	 * 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
	 * 注意: s 和 p中仅包含小写字母
	 */
	virtual std::vector<int> findAnagrams(std::string s, std::string p) = 0;
};


class FindAllAnagramsInAString
{
public:
	class SlidingWindow:public IFindAllAnagramsInAString
	{
	public:
		std::vector<int> findAnagrams(std::string s, std::string p) override
		{
			if (s.empty() || p.empty())
				return {};
			const int sSize = s.size();
			const int pSize = p.size();

			//统计下p中每个字符出现的次数
			std::unordered_map<char, int> charsOfP;
			for (int i = 0; i < pSize; ++i)
				charsOfP[p[i]]++;

			//每中字符的出现次数都满足时的比特位标识
			int expectBitsFlag = 0;
			for (const auto& kvp : charsOfP)
				expectBitsFlag |= 1 << (kvp.first - 'a');

			//要返回的结果
			std::vector<int> ans;
			//滑动窗口中的子串中的字符是否满足个数的比特位标识
			int bitFlag = 0;
			//滑动窗口中每种字符出现的次数
			std::unordered_map<char, int> charsOfS;
			//滑动窗口指针
			int left = 0;
			for (int right = 0; right < sSize; ++right)
			{
				const char& newCh = s[right];
				//出现了不在p中的字符
				if (charsOfP.count(newCh) == 0)
				{
					bitFlag = 0;
					charsOfS.clear();
					left = right + 1;
					continue;
				}
				//加入右边界扩展的字符
				charsOfS[newCh]++;
				if (charsOfS[newCh] > charsOfP[newCh])
				{
					//收缩左边界
					while (charsOfS[newCh] > charsOfP[newCh])
					{
						const char& removeCh = s[left++];
						charsOfS[removeCh]--;
						//移除removeCh的完成bit标识
						if (charsOfS[removeCh] != charsOfP[removeCh])
							bitFlag &= ~(1 << (removeCh - 'a'));
					}
				}
				else if (charsOfS[newCh] == charsOfP[newCh])
				{
					bitFlag |= 1 << (newCh - 'a');
				}

				//收集结果
				if ((bitFlag & expectBitsFlag) == expectBitsFlag)
					ans.push_back(left);
			}
			return ans;
		}
	};

	class DifferSlidingWindow:public IFindAllAnagramsInAString
	{
	public:
		//利用差分思想优化的滑动窗口
		//统计滑动窗口和字符串 p 中每种字母数量的差；并引入变量 differ 来记录当前窗口与字符串 p 中数量不同的字母的个数，并在滑动窗口的过程中维护它。
		//在判断滑动窗口中每种字母的数量与字符串 p 中每种字母的数量是否相同时，只需要判断differ 是否为零即可。
		std::vector<int> findAnagrams(std::string s, std::string p) override
		{
			if (s.empty() || p.empty() || s.size() < p.size())
				return {};
			const int sSize = s.size();
			const int pSize = p.size();

			//26个字母的相差个数的滑动窗口，正数表示多出来的，负数表示欠着的，0表示刚好满足
			std::vector<int> differ(26, 0);
			for (int i = 0; i < pSize; ++i)
			{
				//出现在p串中的字符-1
				differ[p[i] - 'a']--;
				//出现在s串中的字符+1
				differ[s[i] - 'a']++;
			}
			//滑动窗口中不满足的字符个数，为0时表示当前的滑动窗口和p满足同字母异位
			int failedCount = differ.size();
			for (const int charDiffered : differ)
				if (charDiffered == 0)
					failedCount--;

			//要返回的结果，每个同字母异位的子串的开始索引
			std::vector<int> ans;
			//首个子串是否满足?
			if (failedCount == 0)
				ans.push_back(0);
			//滑动窗口,s[i]将移出左边界,s[i+pSize]将移入右边界
			for (int i = 0; i < sSize - pSize; ++i)
			{
				//左边界移出
				int& differLeft = differ[s[i] - 'a'];
				if (differLeft == 1)  failedCount--; //从不满足变为满足
				else if (differLeft == 0) failedCount++;  //从满足变为不满足
				differLeft--;

				//右边界移入
				int& differRight = differ[s[i + pSize] - 'a'];
				if (differRight == -1) failedCount--; //从不满足变为满足
				else if (differRight == 0) failedCount++;
				differRight++;

				//收集结果
				if (failedCount == 0)
					ans.push_back(i + 1);
			}

			return ans;
		}
	};
};